package com.xinpan.exercise;

import java.util.ArrayList;

public class PathSum2 {
    public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if(root == null)
            return res;
        
        
        if(root.left == null && root.right == null)
        {
            if(root.val == sum)
            {
                ArrayList<Integer> aRes = new ArrayList<Integer>();
                aRes.add(root.val);
                res.add(aRes);
                return res;
            }
            else
                return res;
        }
        ArrayList<Integer> aRes = new ArrayList<Integer>();
        aRes.add(root.val);
        
        if(root.left != null)
            subSum(root.left, res, (ArrayList<Integer>)aRes.clone(), sum-root.val);
        if(root.right != null)
            subSum(root.right, res, aRes, sum-root.val);
            
            
        return res;
    }
    
    public void subSum(TreeNode root,  ArrayList<ArrayList<Integer>> res,
                     ArrayList<Integer> aRes, int sum)
    {   
        aRes.add(root.val);
        if(root.left == null && root.right == null)
        {
            if(root.val == sum)
            {
                res.add(aRes);
            }
        }
        
        
        if(root.left != null)
            subSum(root.left, res, (ArrayList<Integer>)aRes.clone(), sum-root.val);
        if(root.right != null)
            subSum(root.right, res, aRes, sum-root.val);
    }
    class TreeNode {
    	      int val;
    	      TreeNode left;
    	      TreeNode right;
    	      TreeNode(int x) { val = x; }
    	  }
}
